Міністерство освіти України
Національний університет «Львівська політехніка»
Кафедра автоматизованих систем управління
МЕТОДИЧНІ ВКАЗІВКИ
З практичних робіт
з дисципліни "Моделювання систем"
для студентів базового напрямку 6.050101 “Комп’ютерні науки”
Львів 2011
Імітаційне моделювання процесу функціонування скінченого дискретного стохастиного автомата. Методичні вказівки до лабораторної роботи з дисципліни “Моделювання систем” для студентів базового напрямку 6.050101 “Комп’ютерні науки”/ Укладач: к.т.н., доцент кафедри АСУ Кузьмін О.В. – Львів, Національний університет “Львівська політехніка”, 9 с.
Укладач: Кузьмін Олександр Васильович
Відповідальний за випуск: к.т.н., доцент Шпак З.Я.
Рецензент: д.т.н., професор Різник В.В.
Методичні вказівки затверджено на засіданні кафедри АСУ
Протокол № 2-2011/2012 від 20 вересня 2011 р.
ПРАКТИЧНЕЕ ЗАНЯТТЯ 3. ДИСКРЕТНО-СТОХАСТИЧНІ МОДЕЛІ (Р-СХЕМИ).
Розглянемо даний підхід на прикладі ймовірнісних автоматів. Ймовірнісний автомат можна визначити як дискретний потактовий перетворювач інформації з пам’ятю, функціонування якого в кожному такті залежить тільки від стану пам’яті і може бути описане статистично. Введемо визначення Р-автомата, використовуючи поняття F-автомата.
Розглянемо множину G, яка представляє собою елементи (zk,zi), де zk – стан, zk Є Z; xi – вхідний сигнал, xi Є X.
Якщо існують функції (zk,xi) і (zk,xi), які відображають множину G відповідно на множини Z і Y (G→Z і G→Y), то говорять, що заданий F-автомат F<Z, X, Y, , >.
В більш загальному виді математичну схему Р-автомата можна представити наступним чином.
Нехай крім множини G задана множина Ф(zk,yj). Тоді якщо існує відображення множини G на множину F у вигляді закону розподілу для кожного елемента (zk,xi), то говорять, що заданий ймовірнісний Р-автомат.
Цей закон розподілу можна представити у вигляді таблиці:
j - кількість вихідних сигналів.
Приклад.
Х={x1, x2}
Z={z0, z1, z2}
Y={y1, y2}
Кількість таких розподілів дорівнює кількості елементів множини G. Тому ймовірнісний автомат P можна представити як P<Z, X, Y, B>. В- сукупність розподілів.
Нехай елементи множини G визначають деякі закони розподілу на підмножини Y, Z.
умови нормування.
Якщо для всіх значень l і q виконується умова lkqj=bkj, то такий ймовірнісний автомат називається ймовірнісним автоматом Мілі. Ця вимога означає виконання умови незалежності розподілів для нового стану Р-автомата і його вихідного сигналу.
Нехай тепер значення вихідного сигналу Р-автомата залежить тільки від стану, в якому знаходиться автомат в даний момент часу.
Якщо для будь-якого к і j виконується lksj=bkj, то такий ймовірнісний автомат називається автоматом Мура.
Якщо вихідний сигнал P-автомата визначається детерміновано, то такий автомат називається Y- детермінованим P- автоматом .
Z- детермінованим ймовірнісним автоматом називається Р- автомат, у якого вибір нового стану є детермінованим.
Розглянемо Y-детермінований Р-автомат, який задається таблицею переходів Р і таблицею виходів.
, d - початкові умови.
Будемо вважати, що до початку роботи Р-автомат завжди знаходиться в стані z0 і в нульовий такт часу міняє стан у відповідності з розподілом D. Інформацію про початковий стан зручно внести в матрицю Р змінивши її розмірність до (к+1) (к+1). Перша стрічка, яка буде співставлятися з z0 буде мати вигляд: 0, d1, d2, ... , dk, а перший стовбець буде нульовим. Описаний Y-детермінований Р-автомат можна задавати у вигляді орієнтованого графа, вершини якого співставляються станам автомата, а дуги - можливим переходам з одного стану в другий. Дуги мають вагу, яка відповідає ймовірності переходу pij. Біля вершин графа записуються значення вихідних сигналів, які викликаються цими станами. Задання Y-детермінованого Р-автомата еквівалентне заданню деякого дискретного марківського ланцюга із скінченою множиною станів. Тому апарат марківських ланцюгів є основним для використання Р-схем для аналітичних розрахунків.
Розглянем...
